package 回溯;

import java.util.*;

public class q332重新安排行程 {

    public static void main(String[] args) {

        List<List<String>> tickets = new ArrayList<>();
        tickets.add(Arrays.asList("MUC", "LHR"));
        tickets.add(Arrays.asList("JFK", "MUC"));
        tickets.add(Arrays.asList("SFO", "SJC"));
        tickets.add(Arrays.asList("JFK", "ALK"));
        tickets.add(Arrays.asList("JFK", "BLK"));
        tickets.add(Arrays.asList("ALK", "LHR"));
        Solution solution = new q332重新安排行程().new Solution();
        solution.findItinerary(tickets);
    }
    class Solution {
        private Deque<String> res;
        private Map<String, Map<String, Integer>> map;

        public List<String> findItinerary(List<List<String>> tickets) {
            // 先构造map
            map = new HashMap<>();
            res = new LinkedList<>();
            for (List<String> t : tickets) {
                String start = t.get(0);
                Map<String, Integer> temp;
                if (map.containsKey(start)) {
                    temp = map.get(start);
                    temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
                } else {
                    temp = new TreeMap<>();// 自动按key的 ？大小  升序排列Map
                    temp.put(t.get(1), 1);
                }
                map.put(start, temp);
            }
            res.add("JFK");
            backTracking(tickets.size());
            return new ArrayList<>(res);
        }

        boolean backTracking(int ticketNum) {
            if (res.size() == ticketNum + 1) return true;

            Map<String, Integer> temp = map.get(res.getLast());
            if(temp == null) return false;
            for ( Map.Entry<String, Integer> entry : temp.entrySet()) {
                if (entry.getValue() == 0) continue;
                res.add(entry.getKey());
                entry.setValue(entry.getValue() - 1);
                if (backTracking(ticketNum)) return true;
                res.removeLast();
                entry.setValue(entry.getValue() + 1);

            }

            return false;
        }
    }

}

